/*
 * CCVisu is a tool for visual graph clustering
 * and general force-directed graph layout.
 * This file is part of CCVisu.
 *
 * Copyright (C) 2005-2012  Dirk Beyer
 *
 * CCVisu is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * CCVisu is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with CCVisu; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Please find the GNU Lesser General Public License in file
 * license_lgpl.txt or http://www.gnu.org/licenses/lgpl.txt
 *
 * Dirk Beyer    (firstname.lastname@uni-passau.de)
 * University of Passau, Bavaria, Germany
 */
package org.sosy_lab.ccvisu.graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.EventObject;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

import org.sosy_lab.ccvisu.Options.Verbosity;
import org.sosy_lab.ccvisu.graph.GraphVertex.Shape;
import org.sosy_lab.ccvisu.graph.Group.GroupKind;
import org.sosy_lab.ccvisu.graph.interfaces.GraphEventListener;
import org.sosy_lab.ccvisu.measuring.ClusterQuality;
import org.sosy_lab.util.Colors;

import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;

/**
 * Contains the representation of a graph.
 * This class is a collection of the data structures needed
 * for layout and transformation processing.
 */
public class GraphData {
  /** Maps a vertex id to a GraphVertex.*/
  private List<GraphVertex>                             vertices;

  /** Maps a vertex name to a GraphVertex. */
  private Map<String, GraphVertex>                      nameToVertex;

  /** Edges of type GraphEdgeInt. Only used if (inFormat < LAY). */
  private List<GraphEdge>                               edges;

  /** Raw RSF data as extracted from input. */
  private Relation                                      tuples;

  /** A cache data structure for getAdjacent. */
  private Map<String, Map<GraphVertex, Set<GraphEdge>>> adjacentCache;

  /** A cache data structure for getAdjacentUndirected. */
  private Map<String, Map<GraphVertex, Set<GraphEdge>>> adjacentCacheUndirected;

  private float                                         degreeMax;
  private float                                         degreeOutMax;

  // List of groups.
  private List<Group>                                   groups;
  private Group                                         defaultGroup;

  /** Notify these observers, when changes occur in the graph */
  protected Collection<GraphEventListener>              onGraphChangeListeners  = new ArrayList<GraphEventListener>();

  public GraphData() {
    reset();
  }

  public void reset() {
    vertices = new ArrayList<GraphVertex>();
    nameToVertex = new HashMap<String, GraphVertex>();
    edges = new ArrayList<GraphEdge>();
    tuples = new Relation();
    adjacentCache = null;
    adjacentCacheUndirected = null;
    degreeMax = 0;
    degreeOutMax = 0;
    groups = new ArrayList<Group>();
    defaultGroup = null;

    notifyAboutGroupsChange(new EventObject(this));
    notifyAboutLayoutChange(new EventObject(this));
  }

  public void setVertices(List<GraphVertex> vertices) {
    this.vertices = vertices;

    // Create the reverse lookup (nameToVertex).
    for (int i = 0; i < vertices.size(); ++i) {
      GraphVertex graphVertex = vertices.get(i);
      graphVertex.setId(i);

      // Add vertex-to-number entry for vertex.
      if (nameToVertex.containsKey(graphVertex.getName())) {
        System.err.println("Input error: Vertex '" + graphVertex.getName()
            + "' exists twice in given input.");
      }
      nameToVertex.put(graphVertex.getName(), graphVertex);
    }

    // Initialize groups.
    initGroups();
  }

  public List<GraphVertex> getVertices() {
    return Collections.unmodifiableList(vertices);
  }

  public GraphVertex getVertexByName(String vertexName) {
    return nameToVertex.get(vertexName);
  }

  private void insertEdge(GraphEdge edge) {
    GraphVertex source = edge.getSource();
    GraphVertex target = edge.getTarget();

    source.setDegree(source.getDegree() + edge.getWeight());
    target.setDegree(target.getDegree() + edge.getWeight());
    source.setDegreeOut(source.getDegreeOut() + edge.getWeight());

    edge.setId(edges.size());

    degreeMax = Math.max(degreeMax, source.getDegree());
    degreeOutMax = Math.max(degreeOutMax, source.getDegreeOut());
    edges.add(edge);
  }

  /**
   * @return the edges
   */
  public List<GraphEdge> getEdges() {
    return ImmutableList.copyOf(edges);
  }

  /**
   * @return the Relation associated with this graph.
   */
  public Relation getRelation() {
    return tuples;
  }

  public void applyRelation(Relation relation, Verbosity verbosity) {
    reset();

    tuples = relation;

    List<GraphVertex> vertices = new ArrayList<GraphVertex>();

    // Maps a vertex name to a GraphVertex.
    Map<String, GraphVertex> nameToVertex = new HashMap<String, GraphVertex>();

    int lineNr = 0;
    for (Tuple tuple : relation) {
      lineNr++;
      try {
        List<String> adTuples = tuple.getTupleElements();
          if (adTuples.size() < 2 && verbosity.isAtLeast(Verbosity.WARNING)) {
            System.err.println("Runtime error: Exception while reading "
                + "a graph edge, at line " + lineNr + ":");
            System.err.println("Input graph file needs to follow the RSF format");
            System.err.println("'<graph-name> <source-vertex> <target-vertex> [<weight>]'.");
          }

          // Relation name.
          String edgeRelName = tuple.getRelationName();
          // Source vertex.
          String edgeSource = adTuples.get(0);
          // Target vertex.
          String edgeTarget = adTuples.get(1);
          // Edge weight.
          String edgeWeight = "1.0";

          if (adTuples.size() > 2) {
            edgeWeight = adTuples.get(2);
          }

          GraphVertex source = createOrReturnVertex(vertices, nameToVertex, edgeSource);
          source.setIsSource(true);

          GraphVertex target = createOrReturnVertex(vertices, nameToVertex, edgeTarget);

          float weight = 1.0f;
          try {
            weight = Math.abs(Float.parseFloat(edgeWeight));
          } catch (Exception e) {
            if (verbosity.isAtLeast(Verbosity.WARNINGLIGHT)) {
              System.err.println("RSF warning (if input is a weighted graph): "
                  + "Float expected for relation '"
                  + edgeRelName + "' at '" + edgeWeight
                  + "', at line " + lineNr + ".");
            }
            weight = 1.0f;
          }

          // Insert edge to graph.
          // (Detection of reflexive edges is done by CCVisu.computeLayout().)
          GraphEdge edge = new GraphEdge(edgeRelName, source, target, weight);
          insertEdge(edge);

          if (edge.getWeight() < 0) {
            System.err.println("Invalid graph: edge {" + source.getName() + ","
                + target.getName() + "} " + "has weight: "
                + edge.getWeight() + ".");
          }
      } catch (Exception e) {
        if (verbosity.isAtLeast(Verbosity.WARNING)) {
          System.err.println(e.toString());
        }
      }
    }

    setVertices(vertices);
  }

  private GraphVertex createOrReturnVertex(List<GraphVertex> vertices,
                                          Map<String, GraphVertex> nameToVertex,
                                          String vertexName) {

    if (nameToVertex.containsKey(vertexName)) {
      // Vertex already exists
      return nameToVertex.get(vertexName);

    } else{
      // Insert vertex into graph.
      GraphVertex source = new GraphVertex(vertexName, vertices.size());
      vertices.add(source);
      nameToVertex.put(vertexName, source);
      return source;
    }
  }

  public GraphEdge getEdgeById(int id) {
    for (GraphEdge edge : edges) {
      if (id == edge.getId()) {
        return edge;
      }
    }

    // found no edge with this id
    return null;
  }

  public float getMaxOutdegree() {
    return degreeOutMax;
  }

  public float getMaxDegree() {
    return degreeMax;
  }

  public void setNodesToRandomPositions(Collection<GraphVertex> nodes, int dimensions) {
    // Initialize with random positions.
    for (GraphVertex currVertex : nodes) {
      Position newPosition = new Position();
      newPosition.x = 2 * (float) Math.random() - 1;

      if (dimensions >= 2) {
        newPosition.y = 2 * (float) Math.random() - 1;
      } else {
        newPosition.y = 0;
      }

      if (dimensions == 3) {
        newPosition.z = 2 * (float) Math.random() - 1;
      } else {
        newPosition.z = 0;
      }

      currVertex.setPosition(newPosition);
    }
  }


  public GraphVertex getVertexById(int id) {
    for (GraphVertex vertex : vertices) {
      if (id == vertex.getId()) {
        return vertex;
      }
    }

    // found no vertex with this id
    return null;
  }

  /**
   * Returns the set of adjacent edges
   * for a given vertex and a given relation.
   */
  public Collection<GraphEdge> getAdjacent(GraphVertex graphVertex, String relationName) {

    // Initialize the map.
    if (adjacentCache == null) {
      adjacentCache = new TreeMap<String, Map<GraphVertex, Set<GraphEdge>>>();
    }

    // Look-up the relation name.
    Map<GraphVertex, Set<GraphEdge>> vertexMap = adjacentCache.get(relationName);
    if (vertexMap == null) {
      vertexMap = new HashMap<GraphVertex, Set<GraphEdge>>();
      adjacentCache.put(relationName, vertexMap);
    }

    // Look-up the vertex.
    Set<GraphEdge> edgeSet = vertexMap.get(graphVertex);
    if (edgeSet == null) {
      edgeSet = new TreeSet<GraphEdge>();
      vertexMap.put(graphVertex, edgeSet);
      for (GraphEdge graphEdge : edges) {
        try {
          if (graphEdge.getSource() == graphVertex && graphEdge.getRelName().matches(relationName)) {
            edgeSet.add(graphEdge);
          }
        } catch (Exception pException) {
          System.err.println("Exception in RegExp match: " + pException.getMessage());
        }
      }
    }
    return edgeSet;
  }

  /**
   * Returns the set of adjacent edges (incoming and outgoing)
   * for a given vertex and a given relation.
   */
  public Collection<GraphEdge> getAdjacentUndirected(GraphVertex graphVertex, String relationName) {

    // Initialize the map.
    if (adjacentCacheUndirected == null) {
      adjacentCacheUndirected = new TreeMap<String, Map<GraphVertex, Set<GraphEdge>>>();
    }

    // Look-up the relation name.
    Map<GraphVertex, Set<GraphEdge>> vertexMap = adjacentCacheUndirected.get(relationName);
    if (vertexMap == null) {
      vertexMap = new HashMap<GraphVertex, Set<GraphEdge>>();
      adjacentCacheUndirected.put(relationName, vertexMap);
    }

    // Look-up the vertex.
    Set<GraphEdge> edgeSet = vertexMap.get(graphVertex);
    if (edgeSet == null) {
      edgeSet = new TreeSet<GraphEdge>();
      vertexMap.put(graphVertex, edgeSet);
      for (GraphEdge graphEdge : edges) {
        try {
          if ((graphEdge.getSource() == graphVertex || graphEdge.getTarget() == graphVertex)
              && graphEdge.getRelName().matches(relationName)) {

            edgeSet.add(graphEdge);
          }
        } catch (Exception pException) {
          System.err.println("Exception in RegExp match: " + pException.getMessage());
        }
      }
    }
    return edgeSet;
  }

  public Group findGroupOfVertex(GraphVertex vertex) {
    for (Group g: groups) {
      if (g.contains(vertex)) {
        return g;
      }
    }
    return null;
  }

  /**
   * Initializes the  group representation (of the layout).
   */
  private void initGroups() {
    // Remove existing groups.
    groups.clear();

    // Create the new default-group and add all existing vertices.
    defaultGroup = new Group("Group 'Unassigned'", Colors.GREEN.get(), Shape.DISC, this);
    for (GraphVertex vertex : vertices) {
      defaultGroup.addNode_WO_COLOR(vertex);
    }

    // Add the (initialized) default group to the lists of groups.
    addGroup(defaultGroup);

    //edges annotation
    for (GraphEdge edge : edges) {
      edge.setShowName(false);
    }
  }

  /**
   * add a new group in the list
   * @param group
   */
  public void addGroup(Group group) {
    groups.add(group);
    notifyAboutGroupsChange(new EventObject(this));
  }

  /**
   * remove the group.
   * @param index
   */
  public void removeGroup(Group group) {
    if (group == defaultGroup) {
      return;
    }

    for (GraphVertex v : group.getNodes()) {
      group.removeNode(v, true);
    }
    groups.remove(group);

    notifyAboutGroupsChange(new EventObject(this));
  }

  /**
   * return the group with the specified name
   * @param name
   * @return the group with the specified name
   */
  public Group getGroup(String name) {
    for (Group group : groups) {
      if (group.getName().equals(name)) {
        return group;
      }
    }
    return null;
  }

  public List<Group> getGroups() {
    return ImmutableList.copyOf(groups);
  }

  /**
   * get the number of groups
   * @return return the number of groups
   */
  public int getNumberOfGroups() {
    return groups.size();
  }

  /**
   * get the number of vertices in the graph.
   */
  public int getNumberOfVertices() {
    return this.getVertices().size();
  }

  /**
   * move the group at index one place higher in the list
   * => group drawn sooner
   * @param group that should be moved.
   */
  public void moveGroupUp(Group group) {
    Preconditions.checkNotNull(group);

    int oldIndex = groups.indexOf(group);
    if (oldIndex > 1) {
      groups.remove(oldIndex);
      groups.add(oldIndex - 1, group);
    }

    notifyAboutGroupsChange(new EventObject(this));
  }

  /**
   * move the group at index one place lower in the list
   * => drawn later (more on top)
   * @param gorup that should be moved.
   */
  public void moveGroupDown(Group group) {
    Preconditions.checkNotNull(group);

    int oldIndex = groups.indexOf(group);
    if (oldIndex < groups.size() - 1 && oldIndex > 0) {
      groups.remove(oldIndex);
      groups.add(oldIndex + 1, group);
    }

    notifyAboutGroupsChange(new EventObject(this));
  }

  /**
   * tells the group that the graph has changed => recompute some data
   */
  public void refreshGroups() {
    for (Group group : groups) {
      group.graphChanged();
    }
  }

  public boolean isEdgesAvailable() {
    return !getEdges().isEmpty();
  }

  public Group getDefaultGroup() {
    return this.defaultGroup;
  }

  /**
   * Remove all groups (except the DefaultGroup)
   */
  public void clearGroups() {
    for (Group g : getGroups()) {
      if (g != getDefaultGroup()) {
        removeGroup(g);
      }
    }
  }

  /**
   * Get number of clusters.
   */
  public int getNumberOfClusters() {
    int result = 0;
    Group[] groups = (Group[]) this.groups.toArray();
    for (Group group : groups) {
      if (group.getKind() == GroupKind.CLUSTER) {
        ++result;
      }
    }
    return result;
  }

  /**
   * Calculate the cut of a group/cluster.
   * @param group  The group/cluster for that the cut should be calculated.
   * @return  The calculated cut.
   */
  public int calculateCutOfGroup (Group group) {
    return ClusterQuality.cutOfGroup(group, this);
  }

  /**
   * Cut of the graphs clustering.
   * @return cut.
   */
  public int calculateCutOfClustering() {
    return ClusterQuality.cutOfClustering(this);
  }

  /**
   * Add a observer to the group-change-event.
   * @param observer
   */
  public void addOnGroupChangeListener(GraphEventListener listener) {
    // TODO: Use own listener.
    onGraphChangeListeners.add(listener);
  }

  /**
   * Add a observer to the graph-change-event.
   * @param observer
   */
  public void addOnGraphChangeListener(GraphEventListener listener) {
    onGraphChangeListeners.add(listener);
  }

  /**
   * Notify all listeners about a change in the graph layout.
   */
  public void notifyAboutLayoutChange(EventObject event) {
    // notify the listeners about the layout change.
    for (GraphEventListener listener : onGraphChangeListeners) {
      try {
        listener.onGraphChangedEvent(event);
      } catch (Exception e) {
        // Maybe the listener (i.e., the drawing frame) was closed.
        e.printStackTrace();
        System.exit(0);
      }
    }

    // the groups my have changed too?:
    // -- The barycenters might have been changed!
    // TODO: Really required?
    refreshGroups();
  }

  /**
   * Notify all listeners about a change in the groups.
   */
  public void notifyAboutGroupsChange(EventObject event) {
    // TODO: Use own listener list.
    for (GraphEventListener listener : onGraphChangeListeners) {
      try {
        listener.onGraphChangedEvent(event);
      } catch (Exception e) {
        // Maybe the listener (i.e., the drawing frame) was closed.
        e.printStackTrace();
        System.exit(0);
      }
    }
  }

  public boolean isGraphConnected() {
    return isGraphConnected(".*");
  }

  /**
   * Determine if the graph is connected.
   */
  public boolean isGraphConnected(String pRelationToCheck) {
    // Handle the trivial cases.
    if (vertices.size() <= 1) {
      return true;
    } else if (vertices.size() > 1 && edges.size() == 0) {
      return false;
    }

    Set<GraphVertex> visited = new HashSet<GraphVertex>();
    Deque<GraphVertex> toVisit = new ArrayDeque<GraphVertex>();

    toVisit.add(vertices.get(0));

    while (toVisit.size() > 0){
      GraphVertex u = toVisit.removeFirst();
      if (visited.add(u)) {
        Collection<GraphEdge> adjEdges = getAdjacentUndirected(u, pRelationToCheck);

        for (GraphEdge e : adjEdges) {
          GraphVertex v = e.getSource();
          GraphVertex w = e.getTarget();

          if (v != u) {
            toVisit.add (v);
          }

          if (w != u) {
            toVisit.add (w);
          }
        }
      }
    }

    return visited.size() == vertices.size();
  }

}
